package com.wcj.queue;

import java.util.*;

/**
 * 你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字：
 * '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。
 * 每个拨轮可以自由旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。
 * 每次旋转都只能旋转一个拨轮的一位数字。
 *
 * 锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。
 *
 * 列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，
 * 这个锁将会被永久锁定，无法再被旋转。
 *
 * 字符串 target 代表可以解锁的数字，
 * 你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。
 */
public class 打开转盘锁 {


    public int openLock(String[] deadends, String target) {
        if("0000".equals(target)){
            return 0;
        }
        //将死亡数组存入set集合，方便后面的contain
        Set<String> dead = new HashSet<>();
        for (String deadend : deadends) {
            dead.add(deadend);
        }

        if (dead.contains("0000")){
            return -1;
        }

        //深度
        int step = 0;
        //遍历队列
        Queue<String> queue = new LinkedList<String>();
        queue.offer("0000");
        //已经看过的列表，防止重复入队
        Set<String> seen = new HashSet<>();
        seen.add("0000");

        while (!queue.isEmpty()){
            step++;
            int size = queue.size();
            for (int i = 0; i < size; i++){
                String status = queue.poll();
                for (String nextStatus : get(status)){
                    if (!seen.contains(nextStatus) && !dead.contains(nextStatus)){
                        if (nextStatus.equals(target)){
                            return step;
                        }
                        queue.offer(nextStatus);
                        seen.add(nextStatus);
                    }
                }
            }
        }
        return -1;
    }

    private List<String> get(String status) {
        List<String> ret = new ArrayList<String>();
        char[] chars = status.toCharArray();
        for (int i = 0; i < 4; i++){
            char num = chars[i];
            chars[i] = numPrev(num);
            ret.add(new String(chars));
            chars[i] = numNext(num);
            ret.add(new String(chars));
            chars[i] = num;
        }
        return ret;
    }
    //返回轮盘上，该数的前一个数
    private char numPrev(char num) {
        return num=='0' ? '9' : (char) (num - 1);
    }
    //返回轮盘上，该数的后一个数
    private char numNext(char num) {
        return num=='9' ? '0' : (char) (num + 1);
    }
}





























